import java.util.Arrays;

/**
 * 164. 最大间距
 * https://leetcode-cn.com/problems/maximum-gap/
 * 进阶：桶排序
 */
public class Solutions_164 {
    public static void main(String[] args) {
        int[] nums = {3, 6, 9, 1};  // output: 3
//        int[] nums = {10};  // output: 0

        int result = maximumGap(nums);
        System.out.println(result);
    }

    /**
     * 解法一：Arrays.sort 排序
     */
    public static int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        // 排序 + 线性比较
        Arrays.sort(nums);
        int max = -1;
        for (int i = 1; i < nums.length; i++) {
            // 与前一元素比较得到最大差值
            max = Math.max(max, nums[i] - nums[i - 1]);
        }
        return max;
    }
}
